// 77. 组合
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

// 你可以按 任何顺序 返回答案。
// 输入：n = 4, k = 2
// 输出：
// [
//   [2,4],
//   [3,4],
//   [2,3],
//   [1,2],
//   [1,3],
//   [1,4],
// ]
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
 var combine = function(n, k) {

    // 定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
    let res=[];
    let ans=[];
    // 递归函数的返回值以及参数
    function def(n,k,startIndex){
        // 回溯函数终止条件
        if(ans.length==k){// 数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了
            res.push([...ans]);// 扩展运算符 因为里面不止一个数字
            return;
        }
        // 单层搜索的过程
        for(let i=startIndex;i<=n;i++){// 控制树的横向遍历
            ans.push(i);// 处理节点 
            def(n,k,i+1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            ans.pop();// 回溯，撤销处理的节点
        }
    }
    def(n,k,1);
    return res;
};

// 优化
for(let i=startIndex;i<=n-(k-ans.length)+1;i++){}
// 1. 已经选择的元素个数：path.size();

// 2. 还需要的元素个数为: k - path.size();

// 3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

// 4. 为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。